package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. Subsets
 * leetcode : https://leetcode.com/problems/subsets/
 * Diffculty : Medium
 *
 * 给一个去重的整形数组，求该数组元素的所有子集(包括空集)
 *
 * 解法：四种思路
 * 1)backtracing  DFS
 * 2)bit manipulation
 * 3)no bullshit (https://leetcode.com/problems/subsets/discuss/122645/3ms-easiest-solution-no-backtracking-no-bit-manipulation-no-dfs-no-bullshit)
 * @Author Antony
 * @Since 2018/11/13 15:20
 */
public class SubSets {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2};
        System.out.println(GsonUtil.toJson(subsets(arr)));
//        System.out.println(GsonUtil.toJson(subsets_binaryTree(arr)));
    }

    /**
     * 这其实是BFS
     * leetcode : 1ms - 100.0%
     *
     * 第四种思路。(easy to understand, no other bullshit)
     * 对于每一个元素，我们只有两种方式：
     * 1）选择该元素，把他加到每一个已存在的集合里生成每一个新的集合。
     * 2）不选择该元素。
     * 把两种结果组合起来就是我们要的结果
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int n : nums){
            int currSize = result.size();
            for(int i=0; i<currSize; i++){
                List<Integer> subSet = new ArrayList<>(result.get(i));
                subSet.add(n);
                result.add(subSet);
            }
        }
        return result;
    }


    /**
     * leetcode : 2ms - 43.74%
     * 二叉树, DFS
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets_binaryTree(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        backtrack(result, new ArrayList<>(), 0, nums);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> subList, int index, int[] nums){
        if(index == nums.length){
            return;
        }
        subList.add(nums[index]);
        result.add(new ArrayList<>(subList));
        backtrack(result, subList, index+1, nums);
        subList.remove(subList.size()-1);
        backtrack(result, subList, index+1, nums);

    }
}
